package simple.number;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode-cn.com/problems/add-binary">67. 二进制求和</a>
 * 给你两个二进制字符串，返回它们的和（用二进制表示）。
 * 输入为 非空 字符串且只包含数字 1 和 0。
 * 示例 1:
 *   输入: a = "11", b = "1"
 *   输出: "100"
 * 示例 2:
 *   输入: a = "1010", b = "1011"
 *   输出: "10101"
 * 提示：
 *   每个字符串仅由字符 '0' 或 '1' 组成。
 *   1 <= a.length, b.length <= 10^4
 *   字符串如果不是 "0" ，就都不含前导零。
 * @author 刘学松
 * @date 2021-06-29 17:28
 */
public class 二进制求和 {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        Map<Character, Integer> map = new HashMap<>();
        map.put('1', 1);
        map.put('0', 0);
        int indexA = a.length()-1;
        int indexB = b.length()-1;
        int flag = 0;
        while (indexA >= 0 && indexB >= 0) {
            char charA = a.charAt(indexA);
            char charB = b.charAt(indexB);
            int sum = map.get(charA) + map.get(charB) + flag;
            if (sum>=2) {
                flag = 1;
                sb.insert(0, sum - 2);
            } else {
                flag = 0;
                sb.insert(0, sum);
            }
            indexA--;
            indexB--;
        }
        while (indexA >= 0) {
            if (flag==0) {
                sb.insert(0, a.substring(0, indexA+1));
                break;
            }
            char charA = a.charAt(indexA);
            int sum = map.get(charA) + 1;
            if (sum >= 2) {
                flag = 1;
                sb.insert(0, sum - 2);
            } else {
                flag = 0;
                sb.insert(0, sum);
            }
            indexA--;
        }
        while (indexB >= 0) {
            if (flag==0) {
                sb.insert(0, b.substring(0, indexB+1));
                break;
            }
            char charB = b.charAt(indexB);
            int sum = map.get(charB) + 1;
            if (sum >= 2) {
                flag = 1;
                sb.insert(0, sum - 2);
            } else {
                flag = 0;
                sb.insert(0, sum);
            }
            indexB--;
        }
        if (flag == 1) {
            sb.insert(0, 1);
        }
        return sb.toString();
    }
}
